Airlines must regularly develop flight schedules for each of their aircraft, with each flight requiring the designation of an originating city, a departure time, a destination, and an arrival time. The ordered sequence of flights to which an aircraft is assigned is called an aircraft route. The goal is to develop a collection of aircraft routes that use available aircraft to service all scheduled flights. When an aircraft is unexpectedly diverted, delayed or grounded, aircraft must be reassigned, rescheduled, and rerouted within an as short as possible recovery period to minimize lost revenues, passenger inconvenience, and operational costs.
Prior publications of general interest as background information include the following: "Model To Reduce Airline Schedule Disturbances", by Dusan Teodorovic and Goran Stojkovic, Journal of Transportation Engineering, July/August (1995); "Swapping Applications In A Daily Airline Fleet Assignment", by Kalyan T. Talluri, Transportation Science, Vol. 30, No.3, August (1996); "Optimization And Persistence", by Gerald G. Brown, Robert F. Dell, and R. Kevin Wood, Institute For Operations Research, Interfaces 27: 5 September-October, pp. 15-37 (1997). "Real-Time Decision Support For Integration Of Airline Flight Cancellations And Delays Part I: Mathematical Formulation", by Jia-Ming Cao and Adib Kanafani, Transportation Planning and Technology, Vol.20, pp. 183-199 (1997); "Real-Time Decision Support For Integration Of Airline Flight Cancellations And Delays Part II: Algorithm And Computational Experiments", by Jia-Ming Cao and Adib Kanafani, Transportation Planning and Technology, Vol. 20, pp. 201-217 (1997); "A Lagrangian Relaxation Approach to Assigning Aircraft to Routes in Hub and Spoke Networks", by Mark S. Daskin and Nichlaos D. Panayotopoulos, Transportation Science, vol.23, pp. 91-99, (1989); "System Operations Advisor: A Real-Time Decision Support System for Managing Airline Operations at United Airlines" by Ananda Rakshit, Nirup Krishnamurthy and Gang Yu, Interfaces 26: 2 March-April, pp.50-58, Institute for Operations Research and the Management Sciences (1996); "Model For Operational Daily Airline Scheduling", by Dusan Teodorovic and Goran Stojkovic, Transportation Planning and Technology, vol. 14, pp.273-285, Gordon and Breach Science Publishers Inc. (1990); "Optimal dispatching strategy on an airline network after a schedule perturbation", by Dusan Teodorovic and Slobodan Guberinic, North-Holland European Journal of Operational Research 15, pp. 178-182, Elsevier Science Publishers B.V. (1984); "American Airlines Arrival Slot Allocation System (ASAS)", by Alberto Vasquez-Marquez, Interfaces 21: 1 January-February, pp. 42-61, The Institute of Management Sciences (1991); "The Multi-Airport Ground-Holding Problem In Air Traffic Control", by Peter B. Vranas, Dimitris J. Bertsimas, and Amedeo R. Odoni, Operations Research, vol. 42, No. 2, March-April, Operations Research Society of America (1994); "Airline Scheduling for the Temporary Closure of Airports", by Shangyao Yan and Chung-Gee Lin, Transportation Science, vol. 31, No. 1, pp. 72-82, Institute for Operations Research and the Management Sciences (1997); "Multifleet routing and multistop flight scheduling for schedule perturbation", by Shangyao Yan and Yu-ping Tu, European Journal of Operational Research 103, pp. 155-169 (1997); "A Decision Support Framework For Handling Schedule Perturbation", by Shangyao Yan and Dah-Hwei Yang, Transprn.-B, vol. 30, No. 6, pp.405-419, Elsevier Science Ltd. (1996); "A Decision Support Framework For Multi-Fleet Routing And Multi-Stop Flight Scheduling", by Shangyao Yan and Hwei-Fwa Young, Transpn. Res.-A, vol. 30, No. 5, pp. 379-398, Elsevier Science Ltd. (1996); "Real-Time Mission-Critical Decision Support Systems for Managing and Controlling Airlines' Operations", by Gang Yu, Proceedings of International Conference On Management Science and The Economic Development of China (Hong Kong, 1996); and "On the Airline Schedule Perturbation Problem Caused by the Ground Delay Program", by Songjun Luo and Gang Yu, Transportation Science, vol. 31, No. 4, November 1997, Institute for Operations Research and the Management Sciences (1997).
In "Models And Methods For Managing Airline Irregular Operations", by Michael F. Arguello, Jonathan F. Bard, and Gang Yu, Operations Research In The Airline Industry, pp 1-45, Kluwer Academic Publishers, (1998); and "A GRASP for Aircraft Routing in Response to Groundings and Delays", by Michael F. Arguello, Jonathan F. Bard, and Gang Yu, Journal of Combinatorial Optimization 5, pp 211-228 (1997), a greedy randomized adaptive search procedure (GRASP) including GRASP operations "simple circuit cancellation", "flight route augmentation", and "partial route exchange" are presented. Further, the above publications provide a framework for testing feasibility and calculating marginal values.
The present invention is an improvement over the teachings of the above publications in that a new operation, the Uncancel Operation, as well as combined operations have been created to afford a more diverse and valuable set of solutions . In particular, the Cancel and Uncancel Operation, the Move and Cancel from Source Operation, the Move and Cancel from Target Operation, the Move and Cancel from Source and Target Operation, the Move and Uncancel to Source Operation, the Move and Uncancel to Target Operation, the Swap and Cancel from Source Operation, the Swap and Cancel from Target Operation, the Swap and Cancel from Source and Target Operation, the Swap and Uncancel to Source Operation, the Swap and Uncancel to Target Operation, and the Three-Way Swap Operation afford a user a much broader neighborhood of operations from which more numerous solutions may be generated.
Although the above GRASP publication discloses the use of a marginal value calculator having a simple cost minimization objective., the marginal value calculator used in the current invention, by way of contradistinction, is defined as a dynamic hierarchical calculator that permits the use of multiple, prioritized, and weighted objectives for determining the value of one solution with respect to another.
As a further difference, the above GRASP publication describes a coarse neighborhood search procedure, whereas the method embodied in the current invention is a direct and more comprehensive procedure for deriving a set of solutions.
Furthermore, the above GRASP publication describes a search procedure that visits many solutions, but requires stopping criteria in order to terminate. In addition, the use of a restricted candidate list, and a randomized selection from the list to choose a new solution is described. The current invention does not use a restricted candidate list, has no randomization techniques, and terminates for each marginal value calculator selected upon generation of a first solution that repairs every Grounded Aircraft Route. Further, in the current invention multiple solutions are generated through the use of multiple marginal value calculators, and a decision tree is used for selection among plural marginal value calculators.
In "An Optimization Model for Airlines' Irregular Operations Control", by Gang Yu, Proceedings Of The International Symposium On Optimization Applications In Management And Engineering (Beijing, 1995), the author presents a model for re-routing aircraft in response to irregular operations, but no method for solving the model. The model is a pure mathematical model for multi-commodity network flow with side constraints. Although the model permits canceling, delaying, and swapping of flights, it is not easily solvable, and techniques have yet to be developed for obtaining optimal solutions from the model in real-time. In contrast, the present invention provides a method for solving aircraft re-routing problems within seconds. Further, the method is unrelated to multi-commodity network flow solution techniques.
"A Decision Support Framework for Airline Flight Cancellations and Delays", by Ahmad I. Z. Jarrah, Gang Yu, Nirup Krishnamurthy, and Anada Rakshit, Transportation Science, vol. 27, No.3, August, pp 266-280, Operations Research Society of America (1993), proposes two separate models for re-routing aircraft in response to irregular operations. One model is provided to manage flight delays, and the other contemplates only flight cancellations. The models are presented as minimum cost network flow problems that can be solved readily. However, no integrated cancellation and delay process is presented. In contrast, the present invention addresses both cancellations and delays as it generates solutions, and handles all user requirements and operations constraints within a unified framework. Further, the current invention is not related to minimum cost network flow solution techniques.
"An Optimization Model For Aircraft Routing In Response To Groundings And Delays", by Michael F. Arguello, Jonathan F. Bard, and Gang Yu, submitted for publication (March, 1997), introduces a time-band model for re-routing aircraft in response to irregular operations. The model approximates the operational problem, integrates the handling of delays and cancellations, and is readily solvable. Further, the model is a minimum cost network flow with side constraints, and is solved through use of traditional network flow algorithms that are commercially available in general purpose network and integer program solvers. However, there is no constraint to affect a minimum number of flight routes, and no ability to meet real-time requirements.
In "Balancing User Preferences for Aircraft Schedule Recovery During Airline Irregular Operations", by Benjamin G. Thengvall, Jonathan F. Bard, and Gang Yu, submitted for publication (March, 1998), the authors present a time-space network for modeling the irregular operations re-routing of aircraft. The resulting model handles delays and cancellations simultaneously, and attempts to limit the disruptions to the original aircraft routings. This model is a network flow with side constraints, and it is solved with traditional network flow and integer programming algorithms. Once the problem is modeled, the corresponding mathematical program is solved with commercial, general purpose network and integer program solvers. In contrast, the invention under consideration within the Aircraft Optimization Engine solves the problem at hand differently. It employs a process that generates solutions through the execution of operations on the grounded aircraft routes. It also solves the problem more robustly because it does not limit flight delays to specific time intervals as in the above paper. Additionally, the current invention is more successful at limiting the number of disrupted routings due to the design of the operations. Furthermore, the operations can be executed much more quickly to generate solutions than the methods required to solve network flow models.
The four publications listed above propose network models for representing the underlying operational problem, and rely on network flow techniques for their solution. In contrast, the invention under consideration within the Aircraft Optimization Engine is a solution construction system that generates solutions through the execution of operations on the grounded aircraft routes. Neither the operations, nor the feasibility, nor the marginal value evaluators are related to network flow modeling or their optimization methods.
Additionally, the current invention solves operations problems in real-time by generating solutions through the execution of operations on grounded aircraft routes. Further, the current invention affects no more than two other available flight routes for every grounded flight route that is corrected. Lastly, the current invention is not related to minimum cost network flow or integer program solution techniques.